package q436_findRightInterval;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
    此题重点在于解题的思路 实际上步骤都清晰明确
     */
    public int[] findRightInterval(int[][] intervals) {
        int[] starts = new int[intervals.length], result = new int[intervals.length];
        // 此题除了用map才存储对应起点的编号之外 我们也可以使用一个数组来进行存储
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i][0];
            map.put(starts[i], i);// key 起点值 value 对应序号
        }
        // 排序起点数组
        Arrays.sort(starts);

        for (int i = 0; i < intervals.length; i++) {
            // 取出终点
            int end = intervals[i][1];
            // 用二分查找 在起点数组中找出该数字
            // 在Arrays中有binarySearch方法 参数为一个排序后的数组和一个target
            // 对于该方法有
            // 1 如果在传入的数组中能够找到对应的target 那么返回该target的下标
            // 2 如果找不到但target在数组的范围内 则返回target应插入的位置的负数 但是是从-1开始 （为了避免和返回0冲突）
            // 3 如果不在范围内 则返回- (len + 1)
            int search = Arrays.binarySearch(starts, end);
            // System.out.println(search);
            // 利用map找出其下标
            // 对于方法返回的search 如果它超过了len 则可以直接返回-1
            if (Math.abs(search) <= intervals.length) {
                // 否则考虑search是否为负数 负数有可能达到intervals.length 也就代表要插入到最后一个位置
                // 要注意的是 search是我们利用二分查找找出来的 元素下标
                // 而map存储的是起点值和序号的关系 所以我们要使用starts[search]
                // 并且在其为负数时 这个下标是从-1开始的 所以要减1后去寻找对应的值
                result[i] = search >= 0 ? map.get(starts[search]) : map.get(starts[-search - 1]);
            }else {
                result[i] = -1;
            }
        }

        return result;
    }
}
